package na.learn.java.corepatterns.caching;

import java.util.HashMap;
import java.util.ListIterator;
import java.util.Vector;

import na.learn.java.Logging.CacheLogger;

import org.apache.log4j.Logger;

/**
 * 
 * Salient features:
 * 	1. Cache size can be provided by user.
 *  2. Cleanup process works in background, and adding is not delayed on best-effort basis..
 *     Cleanup thread is triggered whenever vacancy in young queue size is below threashold level.
 *     Getting a key is fast, and updation of FIFO Queue is completed in background.
 * 
 * Data Structures used:
 *  1. (Notify and/or Remove): If the object is of type Cacheable then
 * 		notify it; else simply remove it.
 *  
 *  2. This has following 3 storage structures:
 *    A
 *  	aa.) CompositeKey object composed of key,  birth_Time, end_time.
 *   	a2.) CompositeKeyValue object composed of (value, and CompositeKey).
 *           Composite Key here is used to lookup into FIFO Queue. ( used for housekeeping of Queue.).
 *   
 *    B HashMap to store (Key,CompositeKeyValue) pair.
 *    
 *    C YoungQueue where Keys of new Object will be added.
 *    
 *    D OldQueue where older Keys will be moved.
 *    
 *    New objects( in CompositeKeyValue) are added to keyValueHashMap, against their keys.
 *    And the corresponding CompositeKey is stored in YoungQueue.
 *    A daemon thread (cleaner) does house keeping job of moving / removing keys,
 *     from the 2 queues to make vacancy for new Objects. 
 *    
 * 
 * Algorithm to ADD new Object to cache:
 *  a.) If there is no vacancy in YoungQueue, wait.
 *  b.) If youngQueue has vanancy, add entries as folows:
 *  	b1.) Create a CompositeKey(key, birthTime, timeToLive).
 *  	b2.) Create a CompositeKeyValue(value, CompositeKey).	
 *  	b3.) Add new (Key,CompositeKeyValue) to keyValueHashMap, corresponding CompositeKeyValue to YoungQueue.
 * 		
 * Algorithm to get a value:
 * 		a.) Get CompositeKeyValue for the key. If not found, return null.
 * 		b.) If found, extract value object from corresponding CompositeKeyValue object in HashMap, and return it.
 * 		c.) A parallel thread moves CompositeKeyValue object from its current position in either queue,
 * 			and is moved to tail of younger queue.
 *
 *  Cleanup Algorithm:
 *	    A Daemon thread cleans up in background.
 *		Currently using LRUPhased Cleaner.
 * 
 * 
 * 
 * 
 * 
 * 
 * @author nagrawal2
 * 
 */

public class LRUCache implements Cache {

	// Class Constants
	// Default cache size if not provided by client.
	private static final int DEFAULT_CACHE_SIZE = 20;

	// Default size-ratio of YoungQueue to OldQueue.
	private static final float DEFAULT_YOUNG_RATIO = 0.5f;

	// Default time to live. -1 means forever-in-store if space is available.
	private static final long MAX_TIME_TO_LIVE_MILLISECS = -1l;

	// Will hold Key, CompositeKeyValue pair
	private HashMap keyValueHashMap;

	// Queue to hold CompositeKey
	private FIFOQueue youngKeyQueue;

	// Queue to hold Old CompositeKey
	private FIFOQueue oldKeyQueue;

	// Max size of cache
	private int max_Cache_Size;

	// Size ratio of YoungQueue / max_Cache_Size.
	private float youngRatio;

	// Hold reference to currrent Cleaner algorothm.
	private Cleaner cleaner;

	// Name of this Cache. Default is inherited from Thread-name used to create instance of this Cache.
	private String name;

	// Stores keys for which values are retrived from cache.
	// Postions in FIFO Queue are updatedusing these keys.
	private Vector keyList;

	// Holds reference to cleaner process thread.
	private Thread cleanerThread;

	// Logger instance.
	private static Logger logger;

	// Initialize Logger.
	static {
		logger = CacheLogger.getLogger(LRUCache.class.getName());
	}

	/**
	 * Constructor 1
	 * @param name
	 * @param cleaner
	 */
	public LRUCache(String name, Cleaner cleaner) {
		this(name, DEFAULT_CACHE_SIZE, DEFAULT_YOUNG_RATIO, cleaner);
	}

	/**
	 * Constructor 2
	 * @param name
	 * @param max_Cache_Size
	 * @param cleaner
	 */
	public LRUCache(String name, int max_Cache_Size, Cleaner cleaner) {
		this(name, max_Cache_Size, DEFAULT_YOUNG_RATIO, cleaner);

	}

	/**
	 * Constructor 3
	 * Temporarily private. WIll be made public after resolving working of youngRatio.
	 *  
	 * @param name
	 * @param max_Cache_Size
	 * @param youngRatio
	 * @param cleaner
	 */
	private LRUCache(String name, int max_Cache_Size, float youngRatio, Cleaner cleaner) {

		this.name = name;
		this.cleaner = cleaner;

		adjustSize(max_Cache_Size, youngRatio);
		initMapAndQueue();

		initCleaner();
		logger.info("Instance of LRUCache creaqted.");

	}

	/**
	 * Initialize cleaner Thread which is a daemon for cleaning up the two Queues.
	 *
	 */
	private void initCleaner() {
		if (cleaner != null && !cleaner.isInit())
			cleaner.attach(keyValueHashMap, youngKeyQueue, oldKeyQueue);

		cleanerThread = new Thread(this.cleaner);
		cleanerThread.setDaemon(true);
		cleanerThread.start();

	}

	/**
	 * Initialize keyValueHashMap, and Queues. Set their maximum sizes.
	 *
	 */
	private void initMapAndQueue() {
		keyValueHashMap = new HashMap(max_Cache_Size);

		youngKeyQueue = new FIFOQueue();
		youngKeyQueue.setName("Young Queue");
		oldKeyQueue = new FIFOQueue();
		oldKeyQueue.setName("Old Queue");

		//		 Size of youngQueue. Calculated based on required max_Cache_Size, and YoungRatio.
		//  = (max_Cache_Size * youngRatio)
		int youngQueueSizeLimit = ((int) (this.youngRatio * this.max_Cache_Size));

		//	 Size of oldQueue. Calculated from cache size and adjusted size of young queue.
		// = max_Cache_Size - youngQueueSizeLimit
		int oldQueueSizeLimit = this.max_Cache_Size - youngQueueSizeLimit;

		youngKeyQueue.setThreashold((int) (youngQueueSizeLimit * 0.8));
		oldKeyQueue.setThreashold((int) (oldQueueSizeLimit * 0.8));

		youngKeyQueue.setMaxAllocSize(youngQueueSizeLimit);
		oldKeyQueue.setMaxAllocSize(oldQueueSizeLimit);
		
		logger.debug("Map and Queue initialized.");

	}

	/**
	 * Caclulate and set maximum size for cache, size-ratio of youngQueue to oldQueue.  
	 * @param max_Cache_Size
	 * @param youngRatio
	 */
	private void adjustSize(int max_Cache_Size, float youngRatio) {
		if ((max_Cache_Size <= 0) || (max_Cache_Size >= (Integer.MAX_VALUE - 1)))
			this.max_Cache_Size = DEFAULT_CACHE_SIZE;
		else
			this.max_Cache_Size = max_Cache_Size;

		youngRatio = new Float(((int) (youngRatio * 10)) / 10f).floatValue();

		if (youngRatio < 0.5f || youngRatio > 1.0f)
			this.youngRatio = DEFAULT_YOUNG_RATIO;
		else
			this.youngRatio = youngRatio;
		logger.debug("Size Adjusted.");

	}

	/* - START - Utility methods exposed to public. */
	public Object add(Object key, Object value) {
		return add(key, value, MAX_TIME_TO_LIVE_MILLISECS);
	}

	/**
	 * Create instances of CompositeKey, and CompositeKeyValue.
	 * If cleaner thread is not alive, initialize it.
	 * Lock youngQ, and wait for vacancy there.
	 * Add instances created above to Queue and HashMap, and notify all on youngQ.
	 */
	public Object add(Object key, Object value, long time_To_Live_Millisecs) {
		//		 Contains key, birthTime, and end-time.
		CompositeKey compositeKey = new CompositeKey(key, time_To_Live_Millisecs);
		//		 Contains, key, COmpositeKey
		CompositeKeyValue cKeyValue = new CompositeKeyValue(value, compositeKey);
		Object cachedValue = null;

		if (!cleanerThread.isAlive())
			initCleaner();

		synchronized (youngKeyQueue) {

			try {
				while (!youngKeyQueue.hasVacancy())
					youngKeyQueue.wait();
				keyValueHashMap.put(key, cKeyValue);
				youngKeyQueue.add(cKeyValue.getCKey());
				cachedValue = value;

			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			youngKeyQueue.notifyAll();

		}
		logger.debug("Added " + key);

		return cachedValue;
	}

	/**
	 * Check if youngQ has vacancy for more objects.
	 * IF its size is less than threashold, objects can be added. 
	 * @return
	 *//*
	private boolean hasVacancy() {
		synchronized (youngKeyQueue) {
			if (youngKeyQueue.size() < youngKeyQueue.getMaxAllocSize())
				return true;
			else
				return false;
		}
	}*/

	/**
	 * Lookup HashMap for key, and if available, 
	 * 	fetch corresponding value from CompositeKeyValue.
	 * Add the key to keyList:Vector.
	 * Start a parallel thread to move this key to top position in queue, and update its time stamp.
	 * Return the key from original thread.
	 *   
	 */
	public Object get(Object key) {
		Object value = null;
		long birthTime = 0L;

		//this.key = key;
		if (keyValueHashMap.containsKey(key) == true) {
			value = ((CompositeKeyValue) keyValueHashMap.get(key)).getValue();
			if (keyList == null)
				keyList = new Vector();
			keyList.add(key);

			(new Thread() {

				public void run() {

					for (ListIterator iter = keyList.listIterator(); iter.hasNext();) {

						CompositeKey compositeKey = ((CompositeKeyValue) keyValueHashMap.get(iter.next())).getCKey();
						synchronized (youngKeyQueue) {

							synchronized (oldKeyQueue) {
								int index = youngKeyQueue.indexOf(compositeKey);
								logger.debug("~~~ Moving Key  ~~~~~~");
								if (index != -1) {
									compositeKey.setBirthTime(System.currentTimeMillis());
									youngKeyQueue.remove(index);
									youngKeyQueue.addLast(compositeKey);
								} else if ((index = oldKeyQueue.indexOf(compositeKey)) != -1) {
									compositeKey.setBirthTime(System.currentTimeMillis());
									oldKeyQueue.remove(index);
									youngKeyQueue.addLast(compositeKey);
								}
								oldKeyQueue.notifyAll();
							}
							youngKeyQueue.notifyAll();
							iter.remove();

						}

					}
				}

			}).start();

			logger.debug("Got value for key: " + key);
		}
		return value;
	}

	/**
	 * Remove entry from Queue and HashMap. 
	 */
	public Object remove(Object key) {
		CompositeKeyValue cKV = null;

		if ((cKV = ((CompositeKeyValue) keyValueHashMap.get(key))) != null) {

			synchronized (youngKeyQueue) {
				if (youngKeyQueue.contains(cKV.getCKey())) {
					keyValueHashMap.remove(key);
					youngKeyQueue.remove(cKV.getCKey());
				}

			}
			synchronized (oldKeyQueue) {
				if (oldKeyQueue.contains(cKV.getCKey())) {
					keyValueHashMap.remove(key);
					oldKeyQueue.remove(cKV.getCKey());
				}

			}

		}

		return cKV == null ? null : cKV.getValue();
	}

	public void clear() {
		// TODO Auto-generated method stub

	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	/**
	 * Print contents of both Queues. 
	 */
	public void print() {
		synchronized (youngKeyQueue) {
			logger.debug("Young Queue contents: ");
			for (ListIterator iter = youngKeyQueue.listIterator(); iter.hasNext();)
				System.out.println(((CompositeKey) iter.next()).getKey());
			youngKeyQueue.notifyAll();

		}

		synchronized (oldKeyQueue) {
			logger.debug("Old Queue contents: ");
			for (ListIterator iter = oldKeyQueue.listIterator(); iter.hasNext();)
				System.out.println(((CompositeKey) iter.next()).getKey());
			oldKeyQueue.notifyAll();

		}

	}

	public String toString() {
		print();
		return super.toString();
	}

	public Cleaner getCleaner() {
		return cleaner;
	}

	public void setCleaner(Cleaner cleaner) {
		this.cleaner = cleaner;
	}

	public int getMax_Cache_Size() {
		return max_Cache_Size;
	}

	public void setMax_Cache_Size(int max_Cache_Size) {
		this.max_Cache_Size = max_Cache_Size;
	}

	/* - END - Utility methods exposed to public. */

}
